package com.cat.greedyAlgorithm;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-number-of-distinct-elements-after-operations/
 * @create 2025/8/22 16:24
 * @since JDK17
 */

public class Solution16 {
    public int maxDistinctElements(int[] nums, int k) {
        if (k == 0) {
            HashSet<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num);
            }
            return set.size();
        }
        Arrays.sort(nums);
        int n = nums.length, min = nums[0] - k, max = nums[n - 1] + k, ans = 0;
        for (int i = 0; i < n; i++) {
            if (min > nums[i] + k) {
                continue;
            }
            min = Math.max(min, nums[i] - k);
            min = Math.max(min + 1, nums[i] - k);
            ans++;
        }
        return ans;
    }
}
